"""
题目：找到双链表的中间节点，如果有两个中间节点，返回第二个。
"""
class Node:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next

def find_middle_node(head):
    # 空链表或单节点链表直接返回
    if not head or not head.next:
        return head

    # 初始化快慢指针
    slow = head
    fast = head

    # 快指针每次走两步，慢指针每次走一步
    while fast and fast.next:
        slow = slow.next  # 慢指针前进一步
        fast = fast.next.next  # 快指针前进两步

    return slow  # 慢指针指向中间节点

# 辅助函数（复用）
def create_doubly_linked_list(arr):
    if not arr:
        return None
    head = Node(arr[0])
    current = head
    for val in arr[1:]:
        new_node = Node(val)
        current.next = new_node
        new_node.prev = current
        current = new_node
    return head

def get_node_value(node):
    return node.val if node else None  # 返回节点值

# 测试
head1 = create_doubly_linked_list([1, 2, 3, 4, 5])
print(get_node_value(find_middle_node(head1)))  # 输出: 3

head2 = create_doubly_linked_list([1, 2, 3, 4, 5, 6])
print(get_node_value(find_middle_node(head2)))  # 输出: 4（两个中间节点时返回第二个）
